package offer

import (
	. "GoLeetcode/common"
)

/*
时间复杂度:O(N+M) l1长度为N,l2长度为M
空间复杂度:O(N+M)

反转系列
https://leetcode-cn.com/problems/lMSNwu/solution/shua-chuan-jian-zhi-offer-day13-lian-bia-cl27/

7->2->5
6->7

725+67 => 计算出来的结果也要按照链表形式返回

由于高位在head,所以通过栈将数字顺序颠倒,从而可以从低位开始相加
技巧点: 每一次先取出栈1和栈2的栈顶元素相加到sum, 然后一个carry记录上一次相加时的进位, sum += carry
然后sum%10 是本位数字, sum/10是新的carry
将本位数字构建新的节点node, 然后node.next = head (head是上一次操作后的头节点)
最后更新head = node
*/

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	stack1, stack2 := make([]int, 0), make([]int, 0)
	for l1 != nil {
		stack1 = append(stack1, l1.Val)
		l1 = l1.Next
	}

	for l2 != nil {
		stack2 = append(stack2, l2.Val)
		l2 = l2.Next
	}

	carry := 0
	head := (*ListNode)(nil)
	for len(stack1) > 0 || len(stack2) > 0 || carry > 0 {
		sum := 0
		if len(stack1) > 0 {
			sum += stack1[len(stack1)-1]
			stack1 = stack1[:len(stack1)-1]
		}
		if len(stack2) > 0 {
			sum += stack2[len(stack2)-1]
			stack2 = stack2[:len(stack2)-1]
		}
		sum += carry
		node := &ListNode{
			Val:  sum % 10,
			Next: head,
		}
		head = node
		carry = sum / 10
	}
	return head
}
